#include <iostream>
using namespace std;

template<typename T>
class Node
{
public:
    Node(T t);
    Node()=default;
    T value;
    Node<T>* lchild;
    Node<T>* rchild;
    Node<T>* parent;
};

template<typename T>
Node<T>::Node(T t)
{
    this->value=t;
    this->lchild= nullptr;
    this->rchild= nullptr;

}

template<typename T>
class Tree
{
public:
    Tree();
    ~Tree();


    Node<T>* search_iterator(T key);//迭代查找
    Node<T>* search_recursion(T key);//遍历查找


    void insert(T key);
    void destory();

private:
    Node<T>* search(Node<T>* &pnode,T key);//遍历查找
    Node<T>* root;//根节点

    void destory(Node<T>* &p);
};

template<typename T>
void Tree<T>::destory()
{
    destory(root);
}

template<typename T>
void Tree<T>::destory(Node<T> *&p)
{
    if(p!= nullptr)
    {
        if(p->lchild!= nullptr)
        {
            destory(p->lchild);
        }
        if(p->rchild!= nullptr)
        {
            destory(p->rchild);
        }
        delete p;
        p= nullptr;
    }
}

template<typename T>
Tree<T>::Tree()
{
    this->root= nullptr;
}

template<typename T>
Tree<T>::~Tree()
{
    destory(root);
}

template<typename T>
void Tree<T>::insert(T key)
{
    Node<T>* pparent= nullptr;
    Node<T>* pnode=root;
    while(pnode!= nullptr)
    {
        pparent=pnode;
        if(key>pnode->value)
        {
            pnode=pnode->rchild;
        }
        else if(key<pnode->value)
        {
            pnode=pnode->lchild;
        }
        else
        {
            cout<<"wrong have same data in this tree";
            break;
        }
    }
    pnode=new Node<T>(key);
    if(pparent == nullptr)
    {
        root=pnode;
    }
    else if(key>pparent->value)
    {
        pparent->rchild=pnode;
    }
    else
    {
        pparent->lchild=pnode;
    }
    pnode->parent=pparent;
}

template<typename T>
Node<T>* Tree<T>::search_iterator(T key) 
{
    Node<T>* pnode=root;
    while (pnode!= nullptr)
    {
        if(pnode->value==key)
        {
            return pnode;
        }
        else if(pnode->value>key)
        {
            pnode=pnode->lchild;
        }
        else if(pnode->value<key)
        {
            pnode=pnode->rchild;
        }

    }
    return nullptr;//没找到
}

template<typename T>
Node<T>* Tree<T>::search_recursion(T key) 
{
    return search(root,key);
}

template<typename T>
Node<T>* Tree<T>::search(Node<T>* &pnode,T key)
{
    if(pnode== nullptr) return nullptr;
    if(pnode->value==key)
    {
        return pnode;
    }
    if(key>pnode->value)
    {
        return search(pnode->rchild,key);
    }
    else
    {
        return search(pnode->lchild,key);
    }
}

int main()
{
    Tree<int> t;
    t.insert(62);
    t.insert(58);
    t.insert(47);
    t.insert(51);
    t.insert(35);
    t.insert(37);
    t.insert(88);
    t.insert(73);
    t.insert(99);
    t.insert(93);
    t.insert(95);
	cout<<t.search_iterator(62)->value;
    return 0;
}